package sort;

/**
 * @Author wangtengyu
 * @Create 2018-09-10-14:22 插入排序，假定第一个数的位置是正确的，后面的数字,就是和前面的比较 如果前面的数字大，前面的数字就往后移一步。直到把前面的数字全比较了。
 */
public class InsertSort {

  public void sort(int[] array) {
    for (int i = 1; i < array.length; i++) {
      //获取要插入的数字
      int target = array[i];

      int j = i;
      //要插入的数字和之前所有的数字进行比较,如果当前插入的数字小于前面的，就进行移动
      while (j > 0 && target < array[j - 1]) {
        array[j] = array[j - 1];
        j--;
      }
      array[j] = target;
    }
  }


  public void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
  }

  public static void main(String[] args) {
    int[] array = new int[]{2, 7, 1, 5, 9, 12, 4};
    InsertSort insertSort = new InsertSort();
    insertSort.sort(array);
    insertSort.printArray(array);
  }
}
